1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| // // 1786 찾기 KMP.cpp // Algorithm // // Created by bbvch13531 on 2018. 3. 31.. // Copyright © 2018년 bbvch13531. All rights reserved. // #define MAX 1000000 #include <cstdio> #include <iostream> #include <string> #include <cstring> #include <vector> using namespace std;
void getPi(string); void kmp(string,string);
vector<int> pi(MAX,0),res;
int main(void){ ios_base::sync_with_stdio(0); cin.tie(NULL); int ansSize; char buf[MAX],ch; string T,P; // scanf("%[^\n]\n",buf); // T=buf; // // scanf("%[^\n]",buf); // P=buf; // scanf는 비공백 문자부터 읽어들인다. 이 부분에서 에러났었음 getline(cin,T); getline(cin,P);
// cout<<T<<endl<<P<<endl; //getc gets 는 c++11이후 버전에서 deprecate되었다. kmp(T,P); ansSize=res.size(); cout<<ansSize<<endl; for(int i=0;i<ansSize;i++) printf("%d ",res[i]+1); return 0; } void getPi(string s){ int n=(int)s.size(),j=0; fill(pi.begin(),pi.end(),0); for(int i=1;i<n;i++){ //substring while(j>0 && s[i]!=s[j]){ j = pi[j-1]; } if(s[i]==s[j]){ j++; pi[i]=j; } } } void kmp(string T,string P){ getPi(P); int n=(int)T.size(),m=(int)P.size(),j=0; for(int i=0;i<n;i++){ while (j>0 && T[i]!=P[j]) { j=pi[j-1]; } if(T[i]==P[j]){ if(j==m-1){ res.push_back(i-j); j=pi[j]; } else j++; } } }
|